package com.example.controlcarappv2;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Labirinto {
	
	// Define o tamanho do Labirinto.
	int iTamanhoX = 3, iTamanhoY = 3;

	// Cria a Matriz para Representar o Labirinto.
	int[][] labirinto = new int[iTamanhoX][iTamanhoY];

	// Tipos de Pecas do Labirinto com relacao as paredes:
	/*- Sem Parede - 0
	- Parede Esquerda - 1
	- Parede Cima - 2
	- Parede Direita - 3
	- Parede Baixo - 4
	- Parede Esquerda & Cima - 5
	- Parede Esquerda & Direita - 6
	- Parede Esquerda & Baixo - 7
	- Parade Cima & Direita - 8
	- Parede Cima & Baixo - 9
	- Parede Direita & Baixo - 10
	- Parede Esquerda & Cima & Direita - 11
	- Parede Esquerda & Cima & Baixo - 12
	- Parede Esquerda & Baixo & Direita - 13
	- Parede Direita & Cima & Baixo - 14
	- Parede Esquerda & Cima & Direita & Baixo - 15*/

	// Seta a posicao Inicial.
	int[] iPosicao = {0, 0};
	
	// Seta a posicao Final.
	int[] iPosicaoFinal = {iTamanhoX-1, iTamanhoY-1};

	// Referencia para encontrar caminho.
	Labirinto anterior = null;

	// iH -> Quantidades de Passos ate o Final.
	// iG -> Quantidades de Passos apartir do Inicio.
	int iH = (iTamanhoX - 1 + iTamanhoY - 1), iG = 0, iF = 0;
	Acao acaoRealizada = null;

	public void geraLabirinto() {

		// Define o total de campos.
		int iTotalCelulas = (labirinto.length * labirinto[0].length);

		// Numero de celulas visitadas.
		int iCelulasVisitadas = 0;

		// Posicao Atual.
		int[] iPosicaoAtual = { 0, 0 };

		// 
		int iQuantidade = 0;
		int[][] posicoesVizinhas = new int[iQuantidade][2];
		int[][] posicoesVisitadas = new int[iTamanhoX][iTamanhoY];
		Stack<int[]> posicoes = new Stack<int[]>();

		// Levanta todas as paredes.
		for (int i = 0; i < iTamanhoX; i++) {
			for (int j = 0; j < iTamanhoY; j++) {
				labirinto[i][j] = 15;
				posicoesVisitadas[i][j] = 0;
			}
		}

		while (iCelulasVisitadas < iTotalCelulas) {

			// Marca a primeira celula como visitada.
			if (posicoesVisitadas[iPosicaoAtual[0]][iPosicaoAtual[1]] == 0){
				iCelulasVisitadas += 1;
				posicoesVisitadas[iPosicaoAtual[0]][iPosicaoAtual[1]] = 1;
				int[] novoInt = {iPosicaoAtual[0], iPosicaoAtual[1]};
				posicoes.push(novoInt);
			}

			// Verifica as celulas vizinhas nao visitadas.
			if ((iPosicaoAtual[0] > 0 && iPosicaoAtual[0] <= (iTamanhoX - 1))
					&& (posicoesVisitadas[iPosicaoAtual[0] - 1][iPosicaoAtual[1]] == 0))
				iQuantidade += 1;
			if ((iPosicaoAtual[0] >= 0 && iPosicaoAtual[0] < (iTamanhoX - 1))
					&& (posicoesVisitadas[iPosicaoAtual[0] + 1][iPosicaoAtual[1]] == 0))
				iQuantidade += 1;
			if ((iPosicaoAtual[1] > 0 && iPosicaoAtual[1] <= (iTamanhoY - 1))
					&& (posicoesVisitadas[iPosicaoAtual[0]][iPosicaoAtual[1] - 1] == 0))
				iQuantidade += 1;
			if ((iPosicaoAtual[1] >= 0 && iPosicaoAtual[1] < (iTamanhoY - 1))
					&& (posicoesVisitadas[iPosicaoAtual[0]][iPosicaoAtual[1] + 1] == 0))
				iQuantidade += 1;

			// Se existe.
			if (iQuantidade > 0) {
				posicoesVizinhas = new int[iQuantidade][2];
				int iVisitado = 0;

				if ((iPosicaoAtual[0] > 0 && iPosicaoAtual[0] <= (iTamanhoX - 1))
						&& (posicoesVisitadas[iPosicaoAtual[0] - 1][iPosicaoAtual[1]] == 0)) {
					posicoesVizinhas[iVisitado][0] = iPosicaoAtual[0] - 1;
					posicoesVizinhas[iVisitado][1] = iPosicaoAtual[1];
					iVisitado += 1;
				}
				if ((iPosicaoAtual[0] >= 0 && iPosicaoAtual[0] < (iTamanhoX - 1))
						&& (posicoesVisitadas[iPosicaoAtual[0] + 1][iPosicaoAtual[1]] == 0)) {
					posicoesVizinhas[iVisitado][0] = iPosicaoAtual[0] + 1;
					posicoesVizinhas[iVisitado][1] = iPosicaoAtual[1];
					iVisitado += 1;
				}
				if ((iPosicaoAtual[1] > 0 && iPosicaoAtual[1] <= (iTamanhoY - 1))
						&& (posicoesVisitadas[iPosicaoAtual[0]][iPosicaoAtual[1] - 1] == 0)) {
					posicoesVizinhas[iVisitado][0] = iPosicaoAtual[0];
					posicoesVizinhas[iVisitado][1] = iPosicaoAtual[1] - 1;
					iVisitado += 1;
				}
				if ((iPosicaoAtual[1] >= 0 && iPosicaoAtual[1] < (iTamanhoY - 1))
						&& (posicoesVisitadas[iPosicaoAtual[0]][iPosicaoAtual[1] + 1] == 0)) {
					posicoesVizinhas[iVisitado][0] = iPosicaoAtual[0];
					posicoesVizinhas[iVisitado][1] = iPosicaoAtual[1] + 1;
					iVisitado += 1;
				}

				// Seleciona uma randomicamente.
				int casaLado = (int) (Math.random() * iQuantidade);

				geraCaminho(iPosicaoAtual, posicoesVizinhas[casaLado]);

				iPosicaoAtual[0] = posicoesVizinhas[casaLado][0];
				iPosicaoAtual[1] = posicoesVizinhas[casaLado][1];

				iQuantidade = 0;
			} else {
				if (!posicoes.isEmpty()){
					int[] novoInt = posicoes.pop();
					iPosicaoAtual[0] = novoInt[0];
					iPosicaoAtual[1] = novoInt[1];
				} else {
					
					int i = 0;
					int j = 0;
					
					do{
						
						i = (int) (Math.random() * (iTamanhoX - 1));
						j = (int) (Math.random() * (iTamanhoY - 1));
						
						iPosicaoAtual[0] = i;
						iPosicaoAtual[1] = j;
						
					}while(posicoesVisitadas[i][j] == 1);
					
				}
			}
		}

	}

	public void geraCaminho(int[] iPosicaoA, int[] iPosicaoB) {

		int blocoA = labirinto[iPosicaoA[0]][iPosicaoA[1]];
		int blocoB = labirinto[iPosicaoB[0]][iPosicaoB[1]];

		// Para Baixo
		if (iPosicaoA[0] == iPosicaoB[0] && iPosicaoA[1] < iPosicaoB[1]) {

			// Verifica Bloco A
			switch (blocoA) {
			case 4:
				blocoA = 0;
				break;
			case 7:
				blocoA = 1;
				break;
			case 9:
				blocoA = 2;
				break;
			case 10:
				blocoA = 3;
				break;
			case 12:
				blocoA = 5;
				break;
			case 13:
				blocoA = 6;
				break;
			case 14:
				blocoA = 8;
				break;
			case 15:
				blocoA = 11;
				break;
			default:
				break;
			}

			// Verifica Bloco B
			switch (blocoB) {
			case 2:
				blocoB = 0;
				break;
			case 5:
				blocoB = 1;
				break;
			case 8:
				blocoB = 3;
				break;
			case 9:
				blocoB = 4;
				break;
			case 11:
				blocoB = 6;
				break;
			case 12:
				blocoB = 7;
				break;
			case 14:
				blocoB = 10;
				break;
			case 15:
				blocoB = 13;
				break;
			default:
				break;
			}
		}

		// Para Cima
		else if (iPosicaoA[0] == iPosicaoB[0] && iPosicaoA[1] > iPosicaoB[1]) {

			// Verifica Bloco A
			switch (blocoA) {
			case 2:
				blocoA = 0;
				break;
			case 5:
				blocoA = 1;
				break;
			case 8:
				blocoA = 3;
				break;
			case 9:
				blocoA = 4;
				break;
			case 11:
				blocoA = 6;
				break;
			case 12:
				blocoA = 7;
				break;
			case 14:
				blocoA = 10;
				break;
			case 15:
				blocoA = 13;
				break;
			default:
				break;
			}

			// Verifica Bloco B
			switch (blocoB) {
			case 4:
				blocoB = 0;
				break;
			case 7:
				blocoB = 1;
				break;
			case 9:
				blocoB = 2;
				break;
			case 10:
				blocoB = 3;
				break;
			case 12:
				blocoB = 5;
				break;
			case 13:
				blocoB = 6;
				break;
			case 14:
				blocoB = 8;
				break;
			case 15:
				blocoB = 11;
				break;
			default:
				break;

			}

		}
		// Para Direita
		else if (iPosicaoA[0] < iPosicaoB[0] && iPosicaoA[1] == iPosicaoA[1]) {
			switch (blocoA) {
			case 3:
				blocoA = 0;
				break;
			case 6:
				blocoA = 1;
				break;
			case 8:
				blocoA = 2;
				break;
			case 10:
				blocoA = 4;
				break;
			case 11:
				blocoA = 5;
				break;
			case 13:
				blocoA = 7;
				break;
			case 14:
				blocoA = 9;
				break;
			case 15:
				blocoA = 12;
				break;
			default:
				break;
			}

			switch (blocoB) {
			case 1:
				blocoB = 0;
				break;
			case 5:
				blocoB = 2;
				break;
			case 6:
				blocoB = 3;
				break;
			case 7:
				blocoB = 4;
				break;
			case 11:
				blocoB = 8;
				break;
			case 12:
				blocoB = 9;
				break;
			case 13:
				blocoB = 10;
				break;
			case 15:
				blocoB = 14;
				break;
			default:
				break;
			}
		}
		// Para Esquerda
		else {
			switch (blocoA) {
			case 1:
				blocoA = 0;
				break;
			case 5:
				blocoA = 2;
				break;
			case 6:
				blocoA = 3;
				break;
			case 7:
				blocoA = 4;
				break;
			case 11:
				blocoA = 8;
				break;
			case 12:
				blocoA = 9;
				break;
			case 13:
				blocoA = 10;
				break;
			case 15:
				blocoA = 14;
				break;
			default:
				break;
			}

			switch (blocoB) {
			case 3:
				blocoB = 0;
				break;
			case 6:
				blocoB = 1;
				break;
			case 8:
				blocoB = 2;
				break;
			case 10:
				blocoB = 4;
				break;
			case 11:
				blocoB = 5;
				break;
			case 13:
				blocoB = 7;
				break;
			case 14:
				blocoB = 9;
				break;
			case 15:
				blocoB = 12;
				break;
			default:
				break;
			}
		}
		
		labirinto[iPosicaoA[0]][iPosicaoA[1]] = blocoA;
		labirinto[iPosicaoB[0]][iPosicaoB[1]] = blocoB;
	}

	List<Acao> acoesPossiveis() {
		List<Acao> retorno = new ArrayList<Acao>();

		int agora = labirinto[iPosicao[0]][iPosicao[1]];

		switch (agora) {
		case 0:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 1:
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 2:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 3:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 4:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			break;
		case 5:
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 6:
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 7:
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			break;
		case 8:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 9:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			break;
		case 10:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			break;
		case 11:
			if (verificaAcaoBaixo())
				retorno.add(new Acao(4));
			break;
		case 12:
			if (verificaAcaoDireita())
				retorno.add(new Acao(2));
			break;
		case 13:
			if (verificaAcaoCima())
				retorno.add(new Acao(3));
			break;
		case 14:
			if (verificaAcaoEsquerda())
				retorno.add(new Acao(1));
			break;
		case 15:
			break;
		default:
			break;
		}

		return retorno;
	}

	Labirinto executaAcao(Acao a) {
		Labirinto retorno = new Labirinto();

		retorno.labirinto = Util.copiaMatrix(this.labirinto);
		retorno.iPosicao[0] = this.iPosicao[0];
		retorno.iPosicao[1] = this.iPosicao[1];

		retorno.iPosicao[0] += a.movimento[0];
		retorno.iPosicao[1] += a.movimento[1];

		retorno.iH = ((iTamanhoX - 1) - retorno.iPosicao[0]) + ((iTamanhoY - 1) - retorno.iPosicao[1]);

		return retorno;
	}

	boolean verificaEstadoFinal() {

		boolean verifica = false;

		if (iPosicao[0] == iPosicaoFinal[0] && iPosicao[1] == iPosicaoFinal[1])
			verifica = true;

		return verifica;
	}

	boolean verificaAcaoEsquerda() {
		if (this.iPosicao[0] > 0 && this.iPosicao[0] <= (iTamanhoX -1)) {
			if ((labirinto[iPosicao[0] - 1][iPosicao[1]] != 3)
					&& (labirinto[iPosicao[0] - 1][iPosicao[1]] != 6)
					&& (labirinto[iPosicao[0] - 1][iPosicao[1]] != 8)
					&& (labirinto[iPosicao[0] - 1][iPosicao[1]] != 10)
					&& (labirinto[iPosicao[0] - 1][iPosicao[1]] != 11)
					&& (labirinto[iPosicao[0] - 1][iPosicao[1]] != 13)
					&& (labirinto[iPosicao[0] - 1][iPosicao[1]] != 14)) {
				return true;
			}
		}
		return false;
	}

	boolean verificaAcaoDireita() {
		if (iPosicao[0] >= 0 && iPosicao[0] < (iTamanhoX -1)) {
			if ((labirinto[iPosicao[0] + 1][iPosicao[1]] != 1)
					&& (labirinto[iPosicao[0] + 1][iPosicao[1]] != 5)
					&& (labirinto[iPosicao[0] + 1][iPosicao[1]] != 6)
					&& (labirinto[iPosicao[0] + 1][iPosicao[1]] != 7)
					&& (labirinto[iPosicao[0] + 1][iPosicao[1]] != 11)
					&& (labirinto[iPosicao[0] + 1][iPosicao[1]] != 12)
					&& (labirinto[iPosicao[0] + 1][iPosicao[1]] != 13)) {
				return true;
			}
		}
		return false;
	}

	boolean verificaAcaoCima() {
		if (iPosicao[1] > 0 && iPosicao[1] <= (iTamanhoY -1)) {
			if ((labirinto[iPosicao[0]][iPosicao[1] - 1] != 4)
					&& (labirinto[iPosicao[0]][iPosicao[1] - 1] != 7)
					&& (labirinto[iPosicao[0]][iPosicao[1] - 1] != 9)
					&& (labirinto[iPosicao[0]][iPosicao[1] - 1] != 10)
					&& (labirinto[iPosicao[0]][iPosicao[1] - 1] != 12)
					&& (labirinto[iPosicao[0]][iPosicao[1] - 1] != 13)
					&& (labirinto[iPosicao[0]][iPosicao[1] - 1] != 14)) {
				return true;
			}
		}
		return false;
	}

	boolean verificaAcaoBaixo() {
		if (iPosicao[1] >= 0 && iPosicao[1] < (iTamanhoY -1)) {
			if ((labirinto[iPosicao[0]][iPosicao[1] + 1] != 2)
					&& (labirinto[iPosicao[0]][iPosicao[1] + 1] != 5)
					&& (labirinto[iPosicao[0]][iPosicao[1] + 1] != 8)
					&& (labirinto[iPosicao[0]][iPosicao[1] + 1] != 9)
					&& (labirinto[iPosicao[0]][iPosicao[1] + 1] != 11)
					&& (labirinto[iPosicao[0]][iPosicao[1] + 1] != 12)
					&& (labirinto[iPosicao[0]][iPosicao[1] + 1] != 14)) {
				return true;
			}
		}
		return false;
	}
}